package com.jxm.linear;

/**
 * @Author: jxm
 * @Description: 快慢指针解决单项链表中间值问题
 * @Date: 2022/6/13 23:59
 * @Version: 1.0
 */
public class FastSlow {

    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
        Node<String> seven = new Node<String>("gg", null);
        //完成结点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;

        //获取中间值
        System.out.println("中间值："+getMid(first));
    }

    /**
     * 快慢指针解决单项链表中间值问题
     * @param first
     * @return
     */
    public static String getMid(Node<String> first) {
        //定义快慢两个指针
        Node<String> fast = first; //每次走两步
        Node<String> slow = first; //每次走一步
        //使用两个指针遍历链表，当快指针指向的结点没有下一个结点了，就可以结束了，结束之后，慢指针指向的结点就是中间值
        while (fast != null && fast.next != null){
            //变换快慢指针
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow.item;
    }

    //结点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item; this.next = next;
        }
    }
}
